package reviewAlgorithms.doublePointers;

import java.util.*;

public class TopKFrequent {
    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3,5,5,5,5};
        int k = 2;
        System.out.println(Arrays.toString(topKFrequent(nums,k)));
    }

    public static int[] topKFrequent(int[] nums, int k) {
        if (nums == null) {
            return nums;
        }
        if (k < 0 || k > nums.length){
            return null;
        }
        int[] res = new int[k];
        Map<Integer, Integer> frequentMap = new HashMap<>();
        Queue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(frequentMap::get));

        for (int i = 0; i < nums.length; i++) {
            if (frequentMap.keySet().contains(nums[i])){
                frequentMap.put(nums[i],frequentMap.get(nums[i]) + 1);
            }else frequentMap.put(nums[i],1);
        }
        for (Integer key : frequentMap.keySet()) {
            queue.add(key);
            if (queue.size() > k){
                queue.poll();
            }
        }
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
}
